//时间复杂度分析：
//最好的情况：整个数组被分为两个长度相等的子数组时， 时间复杂度为 O（nlogn）
//最坏的情况：待排序的序列为正序或者逆序，每次划分只得到一个比上一次划分少一个记录的子序列 （退化成冒泡排序的情况）时间复杂度为O（n的平方）
//平均时间复杂度为：O（nlogn）有可能改变相等元素的原始位置，所以快速排序是一种不稳定的排序。



//空间复杂度分析：
//首先就地快速排序使用的空间是O(1)的，也就是个常数级；而真正消耗空间的就是递归调用了，因为每次递归就要保持一些数据；
//最优的情况下空间复杂度为：O(logn)  ；每一次都平分数组的情况
//最差的情况下空间复杂度为：O( n )      ；退化为冒泡排序的情况
//平均 O（nlogn）



//阮一峰的写法，不是最优的
// var quickSort = function(arr) {　　
//     if (arr.length <= 1) { return arr; }　　
//     var pivotIndex = Math.floor(arr.length / 2);　　
//     var pivot = arr.splice(pivotIndex, 1);　　
//     var left = [];　　
//     var right = [];　　
//     for (var i = 0; i < arr.length; i++) {　　　　
//         if (arr[i] < pivot) {
//             left.push(arr[i]);
//         } else {　　　　　　
//             right.push(arr[i]);　　　　
//         }　　
//     }　　
//     return quickSort(left).concat(pivot, quickSort(right));
// };
// var dataArray = [1, 2, 4];
// console.log(quickSort(dataArray));

//改进
// var quickSort = function(arr) {
//     // 如果数组不可在分，则跳出递归
//     if (arr.length <= 1) {
//         return arr;
//     }
//     // 基准值取数组第一个
//     var pivot = arr[0];
//     var left = [];
//     var right = [];
//     for (var i = 1; i < arr.length; i++) {
//         // 小于等于基准值的放在左边,大于基准值的放在右边
//         if (arr[i] <= pivot) {
//             left.push(arr[i]);
//         } else {
//             right.push(arr[i]);
//         }
//     }
//     // 对左右数组递归quickSort，最后合并成一个完整的数组
//     return quickSort(left).concat(pivot).concat(quickSort(right));
// }

//优化空间复杂度 O（logn） https://segmentfault.com/a/1190000015488549

// function quickSort(arr, i, j) {
//     if (i < j) {
//         let left = i;
//         let right = j;
//         let pvo = arr[left];
//         while (i < j) {
//             while (arr[j] >= pvo && i < j) {
//                 j--;
//             }
//             if (i < j) {
//                 arr[i] = arr[j];
//                 i++;
//             }
//             while (arr[i] <= pvo && i < j) {
//                 i++;
//             }
//             if (i < j) {
//                 arr[j] = arr[i];
//                 j--;
//             }
//         }
//         arr[i] = pvo;
//         quickSort(arr, left, i - 1);
//         quickSort(arr, i + 1, right);
//         return arr;
//     }
// }



function quickSort(arr, i, j) {
    if (i < j) {
        let left = i;
        let right = j;
        let pvo = arr[left];
        while (i < j) {
            while (arr[j] > pvo && i < j) {
                j--;
            }
            if (i < j) {
                arr[i] = arr[j];
                i++;
            }
            while (arr[i] < pvo && i < j) {
                i++;
            }
            if (i < j) {
                arr[j] = arr[i];
                j--;
            }
        }
        arr[i] = pvo;
        quickSort(arr, left, i - 1);
        quickSort(arr, i + 1, right);
        return arr;
    }
}





let arr = [23, 2, 32, 1, 23, 2, 1, 23, 1];
quickSort(arr, 0, arr.length - 1);
console.log(arr);